package main

//编写一个程序，通过填充空格来解决数独问题。
//
// 数独的解法需 遵循如下规则：
//
//
// 数字 1-9 在每一行只能出现一次。
// 数字 1-9 在每一列只能出现一次。
// 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
//
//
// 数独部分空格内已填入了数字，空白格用 '.' 表示。
//
//
//
//
//
//
// 示例：
//
//
//输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".
//",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".
//","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6
//"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[
//".",".",".",".","8",".",".","7","9"]]
//输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8
//"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],[
//"4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9",
//"6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4",
//"5","2","8","6","1","7","9"]]
//解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
//
//
//
//
//
//
// 提示：
//
//
// board.length == 9
// board[i].length == 9
// board[i][j] 是一位数字或者 '.'
// 题目数据 保证 输入数独仅有一个解
//
//
//
//
// Related Topics 数组 回溯 矩阵 👍 1146 👎 0

//leetcode submit region begin(Prohibit modification and deletion)

func solveSudoku(board [][]byte) {
	// 行和列中是否已经存在1-9中的某个数值
	var line, column [9][9]bool
	// 对应矩阵中是否存在1-9中的某个数值
	var block [3][3][9]bool
	// 需要填充的位置（i,j）
	var spaces [][2]int

	for i, row := range board {
		for j, b := range row {
			if b == '.' {
				spaces = append(spaces, [2]int{i, j})
			} else {
				// 减一之后才能和从0开始的数组下标对应
				digit := b - '1'
				line[i][digit] = true
				column[j][digit] = true
				block[i/3][j/3][digit] = true
			}
		}
	}

	var dfs func(int) bool
	dfs = func(pos int) bool {
		if pos == len(spaces) {
			return true
		}
		i, j := spaces[pos][0], spaces[pos][1]
		for digit := byte(0); digit < 9; digit++ {
			// 如果这个位置，这个值从未在行列矩阵中出现过，那就继续下一步
			if !line[i][digit] && !column[j][digit] && !block[i/3][j/3][digit] {
				line[i][digit] = true
				column[j][digit] = true
				block[i/3][j/3][digit] = true
				// 记得加一，因为是digit是下标
				board[i][j] = digit + '1'
				// 继续尝试下一个位置
				if dfs(pos + 1) {
					return true
				}
				// 如果后边的无法成功，那当前位置要恢复原状
				line[i][digit] = false
				column[j][digit] = false
				block[i/3][j/3][digit] = false
			}
		}
		// 1-9都试了一遍都不行，那就返回失败
		return false
	}
	dfs(0)
}

//leetcode submit region end(Prohibit modification and deletion)

func solveSudoku2(board [][]byte) {
	var rows, column [9][9]bool
	var boxes [3][3][9]bool
	var space [][2]int

	for i, row := range board {
		for j, a := range row {
			if a == '.' {
				space = append(space, [2]int{i, j})
				continue
			}
			index := a - '1'
			rows[i][index] = true
			column[index][j] = true
			boxes[i/3][j/3][index] = true
		}
	}

	var dfs func(pos int) bool
	dfs = func(pos int) bool {
		if pos == len(space) {
			return true
		}
		i, j := space[pos][0], space[pos][1]
		for index := byte(0); index < 9; index++ {
			if !rows[i][index] && !column[index][j] && !boxes[i/3][j/3][index] {
				rows[i][index] = true
				column[index][j] = true
				boxes[i/3][j/3][index] = true
				board[i][j] = index + '1'
				if dfs(pos + 1) {
					return true
				}
				rows[i][index] = false
				column[index][j] = false
				boxes[i/3][j/3][index] = false
			}
		}
		return false
	}

	dfs(0)
}
